/**
 * 
 */
package string.passed;

import java.util.LinkedList;

/**
 * @author xyyi
 *
 */
public class SimplifyPath {
	/**
	Given an absolute path for a file (Unix-style), simplify it.

	For example,
	path = "/home/", => "/home"
	path = "/a/./b/../../c/", => "/c"
	
	Corner Cases:
	Did you consider the case where path = "/../"?
	In this case, you should return "/".
	Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
	In this case, you should ignore redundant slashes and return "/home/foo".
	» Solve this problem

	[解题思路]
	利用栈的特性，scan the whole path and skip first "/"
	1. 等于“/”，跳过，直接开始寻找下一个element
	2. 等于“.”，什么都不需要干，直接开始寻找下一个element
	3. 等于“..”，弹出栈顶元素，寻找下一个element
	4. 等于其他，插入当前elemnt为新的栈顶，寻找下一个element

	最后，再根据栈的内容，重新拼path。这样可以避免处理连续多个“/”的问题。
	
	 */
	public String simplifyPath(String path) {
		if (path == null || path.isEmpty()) {
			return "";
		}
		int index = 0;
		LinkedList<String> list = new LinkedList<String>();
		while (index < path.length()) {
			while (index < path.length() && path.charAt(index) == '/') {
				index++;
			}
			if (index == path.length()) {
				break;
			}
			int start = index;
			while (index < path.length() && path.charAt(index) != '/') {
				index++;
			}
			String element = path.substring(start, index);
			if (element.equals("..")) {
				if (!list.isEmpty())
					list.removeLast();
			} else if (!element.equals(".")) {
				list.add(element);
			}
		}

		if (list.isEmpty())
			return "/";

		StringBuilder sb = new StringBuilder();
		for (String element : list) {
			sb.append("/").append(element);
		}

		return sb.toString();
	}

	/**
	 * 
	 */
	public SimplifyPath() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
